home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 151-175 / disk_166 / stevie / source / search.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  15KB  |  723 lines
  1. /*
  2.  * STEVIE - Simply Try this Editor for VI Enthusiasts
  3.  *
  4.  * Code Contributions By : Tim Thompson           twitch!tjt
  5.  *                         Tony Andrews           onecom!wldrdg!tony 
  6.  *                         G. R. (Fred) Walter    watmath!watcgl!grwalter 
  7.  */
  8.  
  9. #include "stevie.h"
  10.  
  11. #ifdef AMIGA
  12. #include "/regexp/regexp.h"
  13. #else
  14. #include <regexp.h>        /* Henry Spencer's regular expression
  15.                  * routines */
  16. #endif
  17.  
  18. #ifdef    MEGAMAX
  19. overlay "search"
  20. #endif
  21.  
  22. /*
  23.  * This file contains various searching-related routines. These fall into
  24.  * three groups: string searches (for /, ?, n, and N), character searches
  25.  * within a single line (for f, F, t, T, etc), and "other" kinds of searches
  26.  * like the '%' command, and 'word' searches. 
  27.  */
  28.  
  29. /*
  30.  * String searches 
  31.  *
  32.  * The actual searches are done using Henry Spencer's regular expression
  33.  * library. 
  34.  */
  35.  
  36. #define    BEGWORD    "([^a-zA-Z0-9_]|^)"    /* replaces "\<" in search strings */
  37. #define    ENDWORD    "([^a-zA-Z0-9_]|$)"    /* likewise replaces "\>" */
  38.  
  39. bool_t begword;            /* does the search include a 'begin word'
  40.                  * match */
  41.  
  42. /*
  43.  * mapstring(s) - map special backslash sequences 
  44.  */
  45. static char    *
  46. mapstring(s)
  47.     char           *s;
  48. {
  49.     static char     ns[MAX_COLUMNS + 1];
  50.     char           *p;
  51.  
  52.     begword = FALSE;
  53.  
  54.     for (p = ns; *s; s++) {
  55.     if (*s != '\\') {    /* not an escape */
  56.         *p++ = *s;
  57.         continue;
  58.     }
  59.     switch (*++s) {
  60.       case '/':
  61.         *p++ = '/';
  62.         break;
  63.  
  64.       case '<':
  65.         strcpy(p, BEGWORD);
  66.         p += strlen(BEGWORD);
  67.         begword = TRUE;
  68.         break;
  69.  
  70.       case '>':
  71.         strcpy(p, ENDWORD);
  72.         p += strlen(ENDWORD);
  73.         break;
  74.  
  75.       default:
  76.         *p++ = '\\';
  77.         *p++ = *s;
  78.         break;
  79.     }
  80.     }
  81.     *p++ = NUL;
  82.  
  83.     return ns;
  84. }
  85.  
  86. static LPTR    *
  87. bcksearch(str)
  88.     char           *str;
  89. {
  90.     static LPTR     infile;
  91.     LPTR           *p;
  92.     regexp         *prog;
  93.     char           *s;
  94.     int             i;
  95.     bool_t          want_start = (*str == '^');    /* looking for start of line? */
  96.     char           *match;
  97.  
  98.     /* make sure str isn't empty */
  99.     if (str == NULL || *str == NUL)
  100.     return NULL;
  101.  
  102.     if ((prog = regcomp(str)) == NULL) {
  103.     emsg("Invalid search string");
  104.     return NULL;
  105.     }
  106.     p = Curschar;
  107.     dec(p);
  108.  
  109.     if (begword)        /* so we don't get stuck on one match */
  110.     dec(p);
  111.  
  112.     i = (want_start) ? 0 : p->index;
  113.  
  114.     do {
  115.     s = p->linep->s;
  116.  
  117.     if (regexec(prog, s)) {    /* match somewhere on line */
  118.  
  119.         if (want_start) {    /* could only have been one */
  120.         infile.linep = p->linep;
  121.         infile.index = (int) (prog->startp[0] - s);
  122.         free((char *) prog);
  123.         return (&infile);
  124.         }
  125.         /*
  126.          * Now, if there are multiple matches on this line, we have to
  127.          * get the last one. Or the last one before the cursor, if we're
  128.          * on that line. 
  129.          */
  130.  
  131.         match = prog->startp[0];
  132.  
  133.         while (regexec(prog, prog->endp[0])) {
  134.         if ((i >= 0) && ((prog->startp[0] - s) > i))
  135.             break;
  136.         match = prog->startp[0];
  137.         }
  138.  
  139.         if ((i >= 0) && ((match - s) > i)) {
  140.         i = -1;
  141.         continue;
  142.         }
  143.         infile.linep = p->linep;
  144.         infile.index = (int) (match - s);
  145.         free((char *) prog);
  146.         return (&infile);
  147.     }
  148.     i = -1;
  149.  
  150.     } while ((p = prevline(p)) != NULL);
  151.  
  152.     /*
  153.      * If wrapscan isn't set, bag the search now 
  154.      */
  155.     if (!P(P_WS)) {
  156.     free((char *) prog);
  157.     return NULL;
  158.     }
  159.     /* search backward from the end of the file */
  160.     p = prevline(Fileend);
  161.     do {
  162.     s = p->linep->s;
  163.  
  164.     if (regexec(prog, s)) {    /* match somewhere on line */
  165.  
  166.         if (want_start) {    /* could only have been one */
  167.         infile.linep = p->linep;
  168.         infile.index = (int) (prog->startp[0] - s);
  169.         free((char *) prog);
  170.         return (&infile);
  171.         }
  172.         /*
  173.          * Now, if there are multiple matches on this line, we have to
  174.          * get the last one. 
  175.          */
  176.  
  177.         match = prog->startp[0];
  178.  
  179.         while (regexec(prog, prog->endp[0]))
  180.         match = prog->startp[0];
  181.  
  182.         infile.linep = p->linep;
  183.         infile.index = (int) (match - s);
  184.         free((char *) prog);
  185.         return (&infile);
  186.     }
  187.     if (p->linep == Curschar->linep)
  188.         break;
  189.  
  190.     } while ((p = prevline(p)) != NULL);
  191.  
  192.     free((char *) prog);
  193.     return NULL;
  194. }
  195.  
  196. static LPTR    *
  197. fwdsearch(str)
  198.     char           *str;
  199. {
  200.     static LPTR     infile;
  201.     LPTR           *p;
  202.     regexp         *prog;
  203.     bool_t          want_start = (*str == '^');    /* looking for start of line? */
  204.  
  205.     char           *s;
  206.     int             i;
  207.  
  208.     if ((prog = regcomp(str)) == NULL) {
  209.     emsg("Invalid search string");
  210.     return NULL;
  211.     }
  212.     p = Curschar;
  213.     i = Curschar->index + 1;
  214.     do {
  215.     s = p->linep->s + i;
  216.     i = 0;
  217.  
  218.     if (regexec(prog, s)) {    /* got a match */
  219.         /*
  220.          * If we wanted the start of a line and we aren't really there,
  221.          * then a match doesn't count. 
  222.          */
  223.         if (want_start && (s != p->linep->s))
  224.         continue;
  225.  
  226.         infile.linep = p->linep;
  227.         infile.index = (int) (prog->startp[0] - p->linep->s);
  228.         free((char *) prog);
  229.         return (&infile);
  230.     }
  231.     } while ((p = nextline(p)) != NULL);
  232.  
  233.     /*
  234.      * If wrapscan isn't set, then don't scan from the beginning of the file.
  235.      * Just return failure here. 
  236.      */
  237.     if (!P(P_WS)) {
  238.     free((char *) prog);
  239.     return NULL;
  240.     }
  241.     /* search from the beginning of the file to Curschar */
  242.     for (p = Filemem; p != NULL; p = nextline(p)) {
  243.     s = p->linep->s;
  244.  
  245.     if (regexec(prog, s)) {    /* got a match */
  246.         infile.linep = p->linep;
  247.         infile.index = (int) (prog->startp[0] - s);
  248.         free((char *) prog);
  249.         return (&infile);
  250.     }
  251.     if (p->linep == Curschar->linep)
  252.         break;
  253.     }
  254.  
  255.     free((char *) prog);
  256.     return (NULL);
  257. }
  258.  
  259. static char    *laststr = NULL;
  260. static int      lastsdir;
  261.  
  262. static LPTR    *
  263. ssearch(dir, str)
  264.     int             dir;    /* FORWARD or BACKWARD */
  265.     char           *str;
  266. {
  267.     LPTR           *pos;
  268.  
  269.     if (dir == BACKWARD)
  270.     pos = bcksearch(mapstring(str));
  271.     else
  272.     pos = fwdsearch(mapstring(str));
  273.  
  274.     /*
  275.      * This is kind of a kludge, but its needed to make 'beginning of word'
  276.      * searches land on the right place. 
  277.      */
  278.     if (begword) {
  279.     if (pos->index != 0)
  280.         pos->index += 1;
  281.     }
  282.     if (laststr != str) {
  283.     if (laststr != NULL)
  284.         free(laststr);
  285.     laststr = strsave(str);
  286.     }
  287.     lastsdir = dir;
  288.  
  289.     return pos;
  290. }
  291.  
  292. void
  293. dosearch(dir, str)
  294.     int             dir;
  295.     char           *str;
  296. {
  297.     LPTR           *p;
  298.  
  299.     if ((p = ssearch(dir, str)) == NULL)
  300.     msg("Pattern not found");
  301.     else {
  302.     LPTR            savep;
  303.  
  304.     cursupdate();
  305.     /* if we're backing up, we make sure the line we're on */
  306.     /* is on the screen. */
  307.     setpcmark();
  308.     *Curschar = savep = *p;
  309.     cursupdate();
  310.     }
  311. }
  312.  
  313. void
  314. searchagain(dir)
  315.     int             dir;
  316. {
  317.     if (laststr == NULL)
  318.     beep();
  319.     else
  320.     dosearch(dir, laststr);
  321.  
  322.     lastsdir = dir;
  323. }
  324.  
  325. #define    OTHERDIR(x)    (((x) == FORWARD) ? BACKWARD : FORWARD)
  326.  
  327. void
  328. repsearch(flag)
  329.     bool_t          flag;
  330. {
  331.     int             dir = lastsdir;
  332.  
  333.     if (laststr == NULL)
  334.     beep();
  335.     else
  336.     dosearch(flag ? OTHERDIR(lastsdir) : lastsdir, laststr);
  337.  
  338.     lastsdir = dir;
  339. }
  340.  
  341. /*
  342.  * regerror - called by regexp routines when errors are detected. 
  343.  */
  344. void
  345. regerror(s)
  346.     char           *s;
  347. {
  348.     emsg(s);
  349. }
  350.  
  351. /*
  352.  * Character Searches 
  353.  */
  354.  
  355. static char     lastc = NUL;    /* last character searched for */
  356. static int      lastcdir;    /* last direction of character search */
  357. static int      lastctype;    /* last type of search ("find" or "to") */
  358.  
  359. /*
  360.  * searchc(c, dir, type) 
  361.  *
  362.  * Search for character 'c', in direction 'dir'. If type is 0, move to the
  363.  * position of the character, otherwise move to just before the char. 
  364.  */
  365. bool_t
  366. searchc(c, dir, type)
  367.     char            c;
  368.     int             dir;
  369.     int             type;
  370. {
  371.     LPTR            save;
  372.  
  373.     save = *Curschar;        /* save position in case we fail */
  374.     lastc = c;
  375.     lastcdir = dir;
  376.     lastctype = type;
  377.  
  378.     /*
  379.      * On 'to' searches, skip one to start with so we can repeat searches in
  380.      * the same direction and have it work right. 
  381.      */
  382.     if (type)
  383.     (dir == FORWARD) ? oneright() : oneleft();
  384.  
  385.     while ((dir == FORWARD) ? oneright() : oneleft()) {
  386.     if (gchar(Curschar) == c) {
  387.         if (type)
  388.         (dir == FORWARD) ? oneleft() : oneright();
  389.         return TRUE;
  390.     }
  391.     }
  392.     *Curschar = save;
  393.     return FALSE;
  394. }
  395.  
  396. bool_t
  397. crepsearch(flag)
  398.     int             flag;
  399. {
  400.     int             dir = lastcdir;
  401.     int             rval;
  402.  
  403.     if (lastc == NUL)
  404.     return FALSE;
  405.  
  406.     rval = searchc(lastc, flag ? OTHERDIR(lastcdir) : lastcdir, lastctype);
  407.  
  408.     lastcdir = dir;        /* restore dir., since it may have changed */
  409.  
  410.     return rval;
  411. }
  412.  
  413. /*
  414.  * "Other" Searches 
  415.  */
  416.  
  417. /*
  418.  * showmatch - move the cursor to the matching paren or brace 
  419.  */
  420. LPTR           *
  421. showmatch()
  422. {
  423.     static LPTR     pos;
  424.     int             (*move) (), inc(), dec();
  425.     char            initc = gchar(Curschar);    /* initial char */
  426.     char            findc;    /* terminating char */
  427.     char            c;
  428.     int             count = 0;
  429.  
  430.     pos = *Curschar;        /* set starting point */
  431.  
  432.     switch (initc) {
  433.  
  434.       case '(':
  435.     findc = ')';
  436.     move = inc;
  437.     break;
  438.       case ')':
  439.     findc = '(';
  440.     move = dec;
  441.     break;
  442.       case '{':
  443.     findc = '}';
  444.     move = inc;
  445.     break;
  446.       case '}':
  447.     findc = '{';
  448.     move = dec;
  449.     break;
  450.       case '[':
  451.     findc = ']';
  452.     move = inc;
  453.     break;
  454.       case ']':
  455.     findc = '[';
  456.     move = dec;
  457.     break;
  458.       default:
  459.     return (LPTR *) NULL;
  460.     }
  461.  
  462.     while ((*move) (&pos) != -1) {    /* until end of file */
  463.     c = gchar(&pos);
  464.     if (c == initc)
  465.         count++;
  466.     else if (c == findc) {
  467.         if (count == 0)
  468.         return &pos;
  469.         count--;
  470.     }
  471.     }
  472.     return (LPTR *) NULL;    /* never found it */
  473. }
  474.  
  475. /*
  476.  * findfunc(dir) - Find the next function in direction 'dir' 
  477.  *
  478.  * Return TRUE if a function was found. 
  479.  */
  480. bool_t
  481. findfunc(dir)
  482.     int             dir;
  483. {
  484.     LPTR           *curr;
  485.  
  486.     curr = Curschar;
  487.  
  488.     do {
  489.     curr = (dir == FORWARD) ? nextline(curr) : prevline(curr);
  490.  
  491.     if (curr != NULL && curr->linep->s[0] == '{') {
  492.         setpcmark();
  493.         *Curschar = *curr;
  494.         return TRUE;
  495.     }
  496.     } while (curr != NULL);
  497.  
  498.     return FALSE;
  499. }
  500.  
  501. /*
  502.  * The following routines do the word searches performed by the 'w', 'W',
  503.  * 'b', 'B', 'e', and 'E' commands. 
  504.  */
  505.  
  506. /*
  507.  * To perform these searches, characters are placed into one of three
  508.  * classes, and transitions between classes determine word boundaries. 
  509.  *
  510.  * The classes are: 
  511.  *
  512.  * 0 - white space 1 - letters, digits, and underscore 2 - everything else 
  513.  */
  514.  
  515. static int      stype;        /* type of the word motion being performed */
  516.  
  517. #define    C0(c)    (((c) == ' ') || ((c) == '\t') || ((c) == NUL))
  518. #define    C1(c)    (isalpha(c) || isdigit(c) || ((c) == '_'))
  519.  
  520. /*
  521.  * cls(c) - returns the class of character 'c' 
  522.  *
  523.  * The 'type' of the current search modifies the classes of characters if a 'W',
  524.  * 'B', or 'E' motion is being done. In this case, chars. from class 2 are
  525.  * reported as class 1 since only white space boundaries are of interest. 
  526.  */
  527. static int
  528. cls(c)
  529.     char            c;
  530. {
  531.     if (C0(c))
  532.     return 0;
  533.  
  534.     if (C1(c))
  535.     return 1;
  536.  
  537.     /*
  538.      * If stype is non-zero, report these as class 1. 
  539.      */
  540.     return (stype == 0) ? 2 : 1;
  541. }
  542.  
  543.  
  544. /*
  545.  * fwd_word(pos, type) - move forward one word 
  546.  *
  547.  * Returns the resulting position, or NULL if EOF was reached. 
  548.  */
  549. LPTR           *
  550. fwd_word(p, type)
  551.     LPTR           *p;
  552.     int             type;
  553. {
  554.     static LPTR     pos;
  555.     int             sclass = cls(gchar(p));    /* starting class */
  556.  
  557.     pos = *p;
  558.  
  559.     stype = type;
  560.  
  561.     /*
  562.      * We always move at least one character. 
  563.      */
  564.     if (inc(&pos) == -1)
  565.     return NULL;
  566.  
  567.     if (sclass != 0) {
  568.     while (cls(gchar(&pos)) == sclass) {
  569.         if (inc(&pos) == -1)
  570.         return NULL;
  571.     }
  572.     /*
  573.      * If we went from 1 -> 2 or 2 -> 1, return here. 
  574.      */
  575.     if (cls(gchar(&pos)) != 0)
  576.         return &pos;
  577.     }
  578.     /* We're in white space; go to next non-white */
  579.  
  580.     while (cls(gchar(&pos)) == 0) {
  581.     /*
  582.      * We'll stop if we land on a blank line 
  583.      */
  584.     if (pos.index == 0 && pos.linep->s[0] == NUL)
  585.         break;
  586.  
  587.     if (inc(&pos) == -1)
  588.         return NULL;
  589.     }
  590.  
  591.     return &pos;
  592. }
  593.  
  594. /*
  595.  * bck_word(pos, type) - move backward one word 
  596.  *
  597.  * Returns the resulting position, or NULL if top-of-file was reached. 
  598.  */
  599. LPTR           *
  600. bck_word(p, type)
  601.     LPTR           *p;
  602.     int             type;
  603. {
  604.     static LPTR     pos;
  605.     int             sclass = cls(gchar(p));    /* starting class */
  606.  
  607.     pos = *p;
  608.  
  609.     stype = type;
  610.  
  611.     if (dec(&pos) == -1)
  612.     return NULL;
  613.  
  614.     /*
  615.      * If we're in the middle of a word, we just have to back up to the start
  616.      * of it. 
  617.      */
  618.     if (cls(gchar(&pos)) == sclass && sclass != 0) {
  619.     /*
  620.      * Move backward to start of the current word 
  621.      */
  622.     while (cls(gchar(&pos)) == sclass) {
  623.         if (dec(&pos) == -1)
  624.         return NULL;
  625.     }
  626.     inc(&pos);        /* overshot - forward one */
  627.     return &pos;
  628.     }
  629.     /*
  630.      * We were at the start of a word. Go back to the start of the prior
  631.      * word. 
  632.      */
  633.  
  634.     while (cls(gchar(&pos)) == 0) {    /* skip any white space */
  635.     /*
  636.      * We'll stop if we land on a blank line 
  637.      */
  638.     if (pos.index == 0 && pos.linep->s[0] == NUL)
  639.         return &pos;
  640.  
  641.     if (dec(&pos) == -1)
  642.         return NULL;
  643.     }
  644.  
  645.     sclass = cls(gchar(&pos));
  646.  
  647.     /*
  648.      * Move backward to start of this word. 
  649.      */
  650.     while (cls(gchar(&pos)) == sclass) {
  651.     if (dec(&pos) == -1)
  652.         return NULL;
  653.     }
  654.     inc(&pos);            /* overshot - forward one */
  655.  
  656.     return &pos;
  657. }
  658.  
  659. /*
  660.  * end_word(pos, type) - move to the end of the word 
  661.  *
  662.  * There is an apparent bug in the 'e' motion of the real vi. At least on the
  663.  * System V Release 3 version for the 80386. Unlike 'b' and 'w', the 'e'
  664.  * motion crosses blank lines. When the real vi crosses a blank line in an
  665.  * 'e' motion, the cursor is placed on the FIRST character of the next
  666.  * non-blank line. The 'E' command, however, works correctly. Since this
  667.  * appears to be a bug, I have not duplicated it here. 
  668.  *
  669.  * Returns the resulting position, or NULL if EOF was reached. 
  670.  */
  671. LPTR           *
  672. end_word(p, type)
  673.     LPTR           *p;
  674.     int             type;
  675. {
  676.     static LPTR     pos;
  677.     int             sclass = cls(gchar(p));    /* starting class */
  678.  
  679.     pos = *p;
  680.  
  681.     stype = type;
  682.  
  683.     if (inc(&pos) == -1)
  684.     return NULL;
  685.  
  686.     /*
  687.      * If we're in the middle of a word, we just have to move to the end of
  688.      * it. 
  689.      */
  690.     if (cls(gchar(&pos)) == sclass && sclass != 0) {
  691.     /*
  692.      * Move forward to end of the current word 
  693.      */
  694.     while (cls(gchar(&pos)) == sclass) {
  695.         if (inc(&pos) == -1)
  696.         return NULL;
  697.     }
  698.     dec(&pos);        /* overshot - forward one */
  699.     return &pos;
  700.     }
  701.     /*
  702.      * We were at the end of a word. Go to the end of the next word. 
  703.      */
  704.  
  705.     while (cls(gchar(&pos)) == 0) {    /* skip any white space */
  706.     if (inc(&pos) == -1)
  707.         return NULL;
  708.     }
  709.  
  710.     sclass = cls(gchar(&pos));
  711.  
  712.     /*
  713.      * Move forward to end of this word. 
  714.      */
  715.     while (cls(gchar(&pos)) == sclass) {
  716.     if (inc(&pos) == -1)
  717.         return NULL;
  718.     }
  719.     dec(&pos);            /* overshot - forward one */
  720.  
  721.     return &pos;
  722. }
  723.